package com.algrithom.tree.binarytree;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 1650. 二叉树的最近公共祖先 III
 * 
 * @author think
 */
public class Solution2 {
    
    public static void main(String[] args){
        TreeNode<Integer> root = TreeOperUtil.createTree(Arrays.asList(3,5,1,6,2,0,8,null,null,7,4).toArray(new Integer[]{}),0);
        Solution2 solution2 = new Solution2();
        //        TreeNode<Integer> result = solution2.lowestCommonAncestor2(root.getLeftChild(),root.getRightChild());
        TreeNode<Integer> p = root.getLeftChild();
        TreeNode<Integer> q = p.getRightChild().getRightChild();
        TreeNode<Integer> result = solution2.lowestCommonAncestor2(root.getLeftChild(),root.getRightChild());
        System.out.println(result.getValue());
    }
    
    TreeNode<Integer> lowestCommonAncestor(TreeNode<Integer> p,TreeNode<Integer> q){
        TreeNode<Integer> pointP = p;
        TreeNode<Integer> pointQ = q;
        
        while (pointP != pointQ) {
            pointP = Objects.nonNull(pointP.getParent()) ? pointP.getParent() : q;
            pointQ = Objects.nonNull(pointQ.getParent()) ? pointQ.getParent() : p;
        }
        
        return pointP;
    }
    
    TreeNode<Integer> lowestCommonAncestor2(TreeNode<Integer> p,TreeNode<Integer> q){
        Map<Integer,TreeNode<Integer>> map = new HashMap<>();
        while (Objects.nonNull(p)) {
            map.put(p.getValue(),p.getParent());
            p = p.getParent();
        }
        while (Objects.nonNull(q)) {
            if (map.containsKey(q.getValue()) || map.containsValue(q)) {
                return q;
            }
            q = q.getParent();
        }
        return null;
    }
}